﻿#include <iostream>

#define MAX(a,b) (a>b?a:b)

static int longestLengthOfCommonSubString(const char* str1, const char* str2)
{
	if (!str1 || !str2) return 0;

	auto len1 = strlen(str1);
	auto len2 = strlen(str2);
	if (!len1 || !len2) return 0;

	int maxLen = 0;
	int add;
	int i = 0;
	int j = len2 - 1;
	int prev;
	int cur;
	while (true)
	{
		add = 0;
		cur = str1[i + add] == str2[j + add] ? 1 : 0;
		maxLen = MAX(maxLen, cur);
		++add;
		prev = cur;
		while (i + add < len1 && j + add < len2)
		{
			cur = str1[i + add] == str2[j + add] ? prev + 1 : 0;
			maxLen = MAX(maxLen, cur);
			prev = cur;
			++add;
		}

		if (i == len1) break;

		--j;
		if (j < 0)
		{
			j = 0;
			++i;
		}
	}

	return maxLen;
}

/**
 * 请注意区分子串和子序列的不同，给定两个字符串str1和str2，求两个字符串的最长公共子串。
 * 
 * 用到一个技巧：动态规划空间压缩的技巧。
 * 
 * 思路：
 * 求解以str1[i]和str2[j]为结尾的最长公共子串是什么。最长公共子串必须以str1[i]和str2[j]结尾！其中，0≤i<str1.Length, 0≤j<str2.Length
 * 
 * 设str1="aabcaac", str2="aaabccab"
 * 
 *          a  a  a  b  c  c  a  b
 *          0  1  2  3  4  5  6  7  j
 * --------------------------------------
 *    a  0| 1  1  1  0  0  0  1  0
 *    a  1| 1  2  2  0  0  0  1  0
 *    b  2| 0  0  0  3  0  0  0  2
 *    c  3| 0  0  0  0  4  1  0  0
 *    a  4| 1  1  1  0  0  0  2  0
 *    a  5| 1  2  2  0  0  0  1  0
 *    c  6| 0  0  0  0  1  1  0  0
 *       i|
 * 
 * 对于上述表格，先填写i==0和j==0的情况
 * 对于i==0而言，只要str2[j]==str1[i], 则最长长度是1，否则是0；
 * 同理，对于j==0而言，只要str1[i]==str2[j], 则最长长度是1，否则是0；
 * 对于普遍情况，则看str1[i]是否==str2[j], 不相等则直接填写0；相等，则填这个格子左上角, 即(i-1,j-1)的值+1
 * 
 * 压缩技巧:
 * 根据上文的结论，(i,j)的值只与(i-1,j-1)的值有关，则可以使用斜率优化法，进行空间压缩。
 * 对于上述例子，可以先从(0,7)开始依次划斜线计算:
 * (0,7)
 * (0,6)->(1,7)
 * (0,5)->(1,6)->(2,7)
 * (0,4)->(1,5)->(2,6)->(3,7)
 * (0,3)->(1,4)->(2,5)->(3,6)->(4,7)
 * ...
 * (0,0)->(1,1)->(2,2)->(3,3)->(4,4)->(5,5)->(6,6)
 * (1,0)->(2,1)->(3,2)->(4,3)->(5,4)->(6,5)
 * ...
 * (5,0)->(6,1)
 * (6,0)
 * 
 * (0,j)和(i,0)的值都是可以直接算出的，则它们的下一个元素，只要判断是否斜线前一个值+1即可
 */
int main_longestCommonSubString()
{
	auto maxLen = longestLengthOfCommonSubString("yeiu123445uewio", "1213jdj23445p083");
	printf("%d", maxLen);
	return 0;
}